Multi-arbre

Un réseau papillon, un multi-arbre utilisé en calcul distribué, montrant (en rouge) le sous-arbre accessible depuis un de ses nœuds.

En combinatoire et en théorie des ordres, le terme multi-arbre peut décrire l'une des deux structures suivantes : un graphe orienté acyclique dans lequel l'ensemble des sommets accessibles depuis un nœud est toujours un arbre, ou un ensemble partiellement ordonné dans lequel il n'existe pas quatre éléments a, b, c, et d qui forment un sous-ordre en diamant, avec abd et acd mais où b et c sont incomparables (un tel ensemble ordonné est aussi appelé diamond-free poset (ou ordre partiel sans diamant)[1].

  1. Jerrold R. Griggs, Wei-Tian Li et Linyuan Lu, « Diamond-free families », Journal of Combinatorial Theory, Series A, vol. 119, no 2,‎ , p. 310–322 (DOI 10.1016/j.jcta.2011.09.002).

Developed by StudentB